import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

/**
 * 这是 LeetCode 第 27 题 "移除元素" 的解决方案
 */
class Remove_Element {
    /**
     * 方法一：单指针法 (removeElement)：
     * 功能：移除数组中所有等于给定值 val 的元素，并返回新数组的有效长度。
     * 实现逻辑：
     * 使用一个指针 left 来记录新数组的有效部分。
     * 遍历数组，如果当前元素不等于 val，则将其复制到 left 指针位置，并将 left 向前移动一位。
     * 最终返回 left，即为新数组的有效长度。
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(1)，只使用了常数级别的额外空间
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        //时间复杂度O(n)
        //空间复杂度O(1)
        int len = nums.length;
        int left = 0;
        for(int right = 0; right < len; right++){
            if(nums[right] != val){
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }

    /**
     * 方法二：双向双指针法 (removeElement1)：
     * 功能：同样移除数组中所有等于给定值 val 的元素，并返回新数组的有效长度。
     * 实现逻辑：
     * 使用两个指针 left 和 right，分别从数组的两端向中间遍历。
     * 如果 left 指针指向的元素等于 val，则用 right 指针指向的元素覆盖 left 指针的位置，并将 right 向左移动一位。
     * 如果 left 指针指向的元素不等于 val，则将 left 向右移动一位。
     * 当 left 和 right 相遇时，结束遍历，返回 left 作为新数组的有效长度。
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(1)，只使用了常数级别的额外空间。
     *
     * @param nums
     * @param val
     * @return
     */
    public int removeElement1(int[] nums, int val) {
        //时间复杂度O(n)
        //空间复杂度O(1)
        int left = 0;
        int right = nums.length;
        while(left < right){
            if(nums[left] == val){
                nums[left] = nums[right - 1];
                right--;
            } else {
                left ++;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        new Remove_Element().testRemoveElement();
        new Remove_Element().testRemoveElement1();
    }

    public void testRemoveElement() {
        Remove_Element solution = new Remove_Element();

        int[] nums1 = {3, 2, 2, 3};
        int val1 = 3;
        int result1 = solution.removeElement(nums1, val1);
        assertEquals(2, result1);
        assertArrayEquals(new int[]{2, 2, 2, 3}, nums1);

        int[] nums2 = {0, 1, 2, 2, 3, 0, 4, 2};
        int val2 = 2;
        int result2 = solution.removeElement(nums2, val2);
        assertEquals(5, result2);
        assertArrayEquals(new int[]{0, 1, 3, 0, 4, 0, 4, 2}, nums2);

        int[] nums3 = {};
        int val3 = 1;
        int result3 = solution.removeElement(nums3, val3);
        assertEquals(0, result3);
        assertArrayEquals(new int[]{}, nums3);

        int[] nums4 = {1, 1, 1, 1};
        int val4 = 1;
        int result4 = solution.removeElement(nums4, val4);
        assertEquals(0, result4);
        assertArrayEquals(new int[]{1, 1, 1, 1}, nums4);
    }

    public void testRemoveElement1() {
        Remove_Element solution = new Remove_Element();

        int[] nums1 = {3, 2, 2, 3};
        int val1 = 3;
        int result1 = solution.removeElement1(nums1, val1);
        assertEquals(2, result1);
        assertArrayEquals(new int[]{2, 2, 2, 3}, nums1);

        int[] nums2 = {0, 1, 2, 2, 3, 0, 4, 2};
        int val2 = 2;
        int result2 = solution.removeElement1(nums2, val2);
        assertEquals(5, result2);
        assertArrayEquals(new int[]{0, 1, 4, 0, 3, 0, 4, 2}, nums2);

        int[] nums3 = {};
        int val3 = 1;
        int result3 = solution.removeElement1(nums3, val3);
        assertEquals(0, result3);
        assertArrayEquals(new int[]{}, nums3);

        int[] nums4 = {1, 1, 1, 1};
        int val4 = 1;
        int result4 = solution.removeElement1(nums4, val4);
        assertEquals(0, result4);
        assertArrayEquals(new int[]{1, 1, 1, 1}, nums4);
    }
}